package com.fr.lintcode;

public class Q1479 {

	/**
	 * @param map: the map
	 * @return: can you reach the endpoint
	 */
	boolean success = false;

	public boolean reachEndpoint(int[][] map) {
        // Write your code here
    	if(map == null) {
    		return success;
    	}
    	int m = map.length;
    	int n = map[0].length;
    	boolean [][]used = new boolean[m][n];
    	search(0,0, map, used, m,n);
    	return success;
    }

	private void search(int i, int j, int[][] map, boolean[][] used, int m, int n) {
		if(success) {
			return;
		}
		if(map[i][j] == 9) {
			success = true;
			return;
		}
		if(map[i][j] == 0 || used[i][j]) {
			return;
		}
		used[i][j] = true;
		if(i + 1 < m) {
			search(i + 1, j, map, used, m,n);
		}
		if(i - 1 >= 0) {
			search(i - 1, j, map, used, m,n);
		}
		if(j + 1 < n) {
			search(i, j + 1, map, used, m,n);
		}
		if(j - 1 >= 0) {
			search(i, j - 1, map, used, m,n);
		}
	}

}
